package com.ryujung.dfs_backtracking;

import java.util.ArrayList;
import java.util.List;

class Solution93 {


    /**
     * 优化最初题解的运行效率问题
     * 思路：
     * 判断substr是否合法的函数可以被优化掉，在循环中加入适当判断即可
     * dfs中的参数index如果为0，直接返回
     */
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        dfs(s, 0, 0, new StringBuilder(), res);
        return res;
    }

    /**
     * 优化后
     * 解答成功:
     * 	执行耗时:2 ms,击败了73.65% 的Java用户
     * 	内存消耗:41.4 MB,击败了65.03% 的Java用户
     */
    private void dfs(String s, int index, int dotCount, StringBuilder sb, List<String> res) {
        // 如果现有的dot已超过3个，直接返回
        if (dotCount > 4) {
            return;
        }
        // 遍历到结尾
        if (index == s.length()) {
            if (dotCount == 4) {
                res.add(sb.substring(0, sb.length() - 1));
            }
            return;
        }

        for (int i = index; i < index + 3 && i < s.length(); i++) {
            String subStr = s.substring(index, i + 1);
            if (Integer.parseInt(subStr) < 1 << 8) {
                sb.append(subStr).append(".");
                dfs(s, i + 1, dotCount + 1, sb, res);
                sb.delete(sb.length() - subStr.length() - 1, sb.length());
            }
            // 不允许leading zeros作为头部构建多字符的substr，单字符可以例如：0，0，10，0
            if ("0".equals(subStr)) {
                return;
            }
        }
    }

    /**
     * 独立解题，使用dfs，效率太低
     * 解答成功:
     * 执行耗时:7 ms,击败了15.30% 的Java用户
     * 内存消耗:42.4 MB,击败了5.07% 的Java用户
     */
    public List<String> restoreIpAddresses1(String s) {
        List<String> res = new ArrayList<>();
        dfs1(s, 0, 0, new StringBuilder(), res);
        return res;
    }

    private void dfs1(String s, int index, int dotCount, StringBuilder sb, List<String> res) {
        if (index == s.length()) {
            if (dotCount == 3) {
                res.add(sb.toString());
            }
            return;
        }
        for (int i = index; i <= index + 3 && i < s.length(); i++) {
            String subStr = s.substring(index, i + 1);
            if (isValid(subStr)) {
                boolean isEndIndex = i == s.length() - 1;
                sb.append(subStr).append(isEndIndex ? "" : ".");
                dfs1(s, i + 1, dotCount + (isEndIndex ? 0 : 1), sb, res);
                sb.delete(sb.length() - (subStr.length() + (isEndIndex ? 0 : 1)), sb.length());
            }
        }
    }

    private boolean isValid(String s) {
        int len = s.length();
        // can't have leading zeros.
        if (len > 1 && s.charAt(0) == '0') return false;

        int i = Integer.parseInt(s);
        return i >= 0 && i < 1 << 8;
    }

    public static void main(String[] args) {
        System.out.println(1 << 8);
        Solution93 s = new Solution93();
        System.out.println(s.restoreIpAddresses("25525511135"));
        System.out.println(s.restoreIpAddresses("0000"));
        System.out.println(s.restoreIpAddresses("00100"));
    }
}